home *** CD-ROM | disk | FTP | other *** search
/ MacFormat 1994 November / macformat-018.iso / Utility Spectacular / Developer / macgambit-20-compiler-src-p1 / Examples / queens.scm < prev    next >
Encoding:
Text File  |  1994-07-26  |  807 b   |  30 lines  |  [TEXT/gamI]
  1. ; N-queens problem
  2. ;
  3. ; try: (queens 8 #t)
  4.  
  5. (##declare (standard-bindings) (fixnum)) ; Compiler: generate fast code
  6.  
  7. (define (queens n trace?)
  8.  
  9.   (define (1-to n)
  10.     (let loop ((i n) (l '()))
  11.       (if (= i 0) l (loop (- i 1) (cons i l)))))
  12.  
  13.   (define (try x y z)
  14.     (if (null? x)
  15.       (if (null? y) (begin (if trace? (begin (write z) (newline))) 1) 0)
  16.       (let* ((temp1 (if (ok? (car x) 1 z)
  17.                       (try (append (cdr x) y) '() (cons (car x) z))
  18.                       0))
  19.              (temp2 (try (cdr x) (cons (car x) y) z)))
  20.         (+ temp1 temp2))))
  21.  
  22.   (define (ok? row dist placed)
  23.     (if (null? placed)
  24.       #t
  25.       (and (not (= (car placed) (+ row dist)))
  26.            (not (= (car placed) (- row dist)))
  27.            (ok? row (+ dist 1) (cdr placed)))))
  28.  
  29.   (try (1-to n) '() '()))
  30.